#ifndef  _MEMORY_POOL_
#define  _MEMORY_POOL_

#include <stdlib.h>
#include <malloc.h>
#include <vector>
#include <algorithm>
using std::vector;

template<class K, int N>
class MemoryPool {
private:
	vector<K*> memBlocks;
	int total;
	int next;
	vector<K*> avail;
public:
	MemoryPool(): total(N), next(0) {
		memBlocks.push_back( (K*)malloc(sizeof(K) * N) );
	}

	~MemoryPool() {
		destroyPool();
	}

	void destroyPool() {
		if (total == 0) {
			return;
		}
		if (!avail.empty()) {
			sort(avail.begin(), avail.end());
		}
		for (--next; next >=0; --next) {
			if (!avail.empty() && (memBlocks[next / N] + (next % N)) == avail.back()) {
				avail.pop_back();
			} else {
				(memBlocks[next / N] + (next % N))->~K();
			}
		}
		for (int i = 0; i < total / N; ++i) {
			free(memBlocks[i]);
		}
		total = 0;
	}

	void* newPlacement() {
		if (!avail.empty()) {
			K* ret = avail.back();
			avail.pop_back();
			return ret;
		} // if (!avail.empty())
		if (next == total) {
			total += N;
			K* temp = (K*)malloc(sizeof(K) * N);
			if (temp == NULL) {
				throw std::bad_alloc();
			}
			memBlocks.push_back(temp);
		}
		void* placement = memBlocks[next / N] + (next % N);
		++next;
		return placement;
	}

	K* newObject() {
		return new(newPlacement()) K;
	}

	void deleteObject(K* obj) {
		obj->~K();
		avail.push_back(obj);
	}
};

#endif